package NM;

public class text1 {
    //将两个单链表合并为一个新的有序的链表，并返回。新链表是通过拼接给定的两个链表的所有节点组成的；
        public static MyLinkedList.ListNote mergeTwoLists(MyLinkedList.ListNote headA,MyLinkedList.ListNote headB){
            MyLinkedList.ListNote newHead=new MyLinkedList.ListNote(-1);
            MyLinkedList.ListNote tmp=newHead;
            while(headA!=null&&headB!=null) {
                if (headA.val < headB.val) {
                    tmp.next = headA;
                    headA = headA.next;
                    tmp = tmp.next;
                } else {
                    tmp.next = headB;
                    headB = headB.next;
                    tmp = tmp.next;
                }
            }
            if(headA!=null){
                tmp.next=headA;
            }
            if(headB!=null){
                tmp.next=headB;
            }
            return newHead.next;
    }
   /* public static void main(String[]args){
            MyLinkedList myLinkedList1=new MyLinkedList();
            myLinkedList1.addLast(1);
            myLinkedList1.addLast(1);
            myLinkedList1.addLast(2);
            myLinkedList1.addLast(4);
            myLinkedList1.addLast(5);
        MyLinkedList myLinkedList2=new MyLinkedList();
        myLinkedList2.addLast(0);
        myLinkedList2.addLast(2);
        myLinkedList2.addLast(5);
        myLinkedList2.addLast(6);
        myLinkedList2.addLast(9);
         MyLinkedList.ListNote node1=mergeTwoLists( myLinkedList1.head,myLinkedList2.head);
         myLinkedList1.disPlay();


    }*/
    //输入两根链表。找出它们的第一个公共节点。
    public static MyLinkedList.ListNote getIntersectionNode(MyLinkedList.ListNote headA,MyLinkedList.ListNote headB){
        MyLinkedList.ListNote pl=headA;
        MyLinkedList.ListNote ps=headB;
        int lenA=0;
        int lenB=0;
        while(pl!=null){
            lenA++;
            pl=pl.next;
        }
        while(ps!=null){
            lenB++;
            ps=ps.next;
        }
        pl=headA;
        ps=headB;
        //根据计算出的lenA和lenB进行两个链表的长度的判断；
        int len=0;
        len=lenA-lenB;
        if(len<0){
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }
        //让快指针先走差值步；
        while(len!=0){
            pl=pl.next;
            len--;
        }
        //让快慢指针一起走；
        while(pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        if(pl==null){
            return null;
        }
        return pl;
    }


}
